/* exercice 2 */


decomp(1,[]).
decomp(N,[M|L]):-N>1,between(2,N,M), N mod M =:= 0, Q is N//M,decomp(Q,L).

est_premier(N):-setof(X,decomp(N,X),L),L=[[N]].

    /* pred auxiliaire liste croissante inc/1 */
    inc([]).
    inc([_]).
    inc([X,Y|L]):-X=<Y,inc([Y|L]).

    /* pred auxiliaire liste de pemiers  all_primes/1 */
    all_primes([]).
    all_primes([X|L]):-est_premier(X),all_primes(L).

    factor(N,F):-decomp(N,F),inc(F),all_primes(F).

    /* pred auxiliaire intersection avec mult. de listes triees inter/3 */

    inter([],_,[]).
    inter(_,[],[]).
    inter([X|L],[Y|H],G):-X<Y,inter(L,[Y|H],G).
    inter([X|L],[Y|H],G):-X>Y,inter([X|L],H,G).
    inter([X|L],[X|H],[X|G]):-inter(L,H,G).

     /* pred auxiliaire produit des elts d une liste prod/1 */

    prod([],1).
    prod([X|L],N):-prod(L,K),N is X*K.

    pgcd(N,M,P):-factor(N,F),factor(M,G),inter(F,G,H),prod(H,P).

 /* pred auxiliaire union avec mult. de listes triees unio/3 */

    unio([],L,L).
    unio(L,[],L).
    unio([X|L],[Y|H],[X|G]):-X<Y,unio(L,[Y|H],G).
    unio([X|L],[Y|H],[Y|G]):-X>Y,unio([X|L],H,G).
    unio([X|L],[X|H],[X|G]):-unio(L,H,G).

    ppcm(N,M,P):-factor(N,F),factor(M,G),unio(F,G,H),prod(H,P).

/* exercice 3 */

move(t(G,D),T):-T=G;T=D.

wins(T):-move(T,S),not(wins(S)).
 /* pred auxiliaire pour completude aux/2  */

 aux(nil,0).
 aux(t(G,D),H):-aux(G,N),aux(D,N),H is N+1.

complete(T):-aux(T,_).

complete_odd(T):-aux(T,N), N mod 2 =:= 1.

/* pred auxiliaire ; toute les positions d'une liste sont perdantes lose/1  */

lose([]).
lose([X|L]):-not(wins(X)),lose(L).

wins_strongly(P):-setof(Q,move(P,Q),L), length(L,K), K>0, lose(L).